есть 100 женщин и 100 мужчин, и известны некоторые их взаимные симпатии,
можно ли соответственно симпатиям разбить их на 100 пар..?
- наверное, компьютер решит это в минуту..

а вот если бы полов было 3, и требовалось разбить 300 человек на тройки
- на это компьютеру не хватило бы тысячелетий..
потому что, оказывается, это задача другого класса..

так что если озадачиться поиском алгоритма для чего-то подобного,
полезно уметь отличать решаемое от нерешаемого..
и умные дяди уже давно думают как этому научиться:
https://en.wikipedia.org/wiki/Computational_complexity_theory

когда меня ещё не было в планах, великий Кук догадался,
что решение одной задачи может полностью сводиться к решению другой..
и что тогда вторая задача "не проще" первой..
(Cook, S.A. [1971] "The complexity of theorem-proving procedures")

он рассматривал задачи двух типов: P (простые) и NP (непростые),
а потом взял и свёл все непростые задачи к одной:
"Честь быть первой "полной-NP" задачей выпала на долю задачи ВЫПОЛНИМОСТЬ.." (*)

"полная-NP" задача - это если к ней сводятся все задачи NP,
тогда - если сводить ВЫПОЛНИМОСТЬ к другим задачам, а те к третьим..
- все они будут "полными-NP"

(*) цитата из другой знаменитейшей книги
Garey, M.R. [1979] "Computers and Intractability"
(вернее из её переиздательства "МИР" 1982,
ксерокопии из которой раздавал нам даже профессор Мати Томбак,
на что многие студенты справедливо реагировали: "мис асья?!")

"В монографии приводится список известных к тому времени NP-полных задач, насчитывающий уже более 300 наименований.
К настоящему времени количество известных NP-полных задач выражается четырехзначным числом,
и постоянно появляются новые, возникающие как в самой математике и теории сложности,
так и в таких дисциплинах как биология, социология, военное дело, теория расписаний, теория игр и т.д." (**)

нынче доказать какую-нибудь NP-полноту уже настолько не модно,
что этому даже не уделяют статьи в математических журнальчиках, ага

"Доказательства NP-полноты являются скорее искусством,
и мы от всей души желаем нашим читателям больше полиномиальных (P) алгоритмов,
хороших и разных, для интересующих их задач
с тем, чтобы обращаться к этому специфическому искусству им пришлось как можно реже." (**)

(**) а это цитаты из курса лекций Кузюрина и Фомина, рассматривать который можно здесь:
https://sites.google.com/site/isprascourses/algorithms-complexity

а теперь наконец - во что мы упираемся:
до сих пор неизвестно, являются ли задачи NP на самом деле труднорешаемыми:
различны ли классы P и NP:

"Безуспешным попыткам построения полиномиальных алгоритмов для NP-полных задач
были посвящены усилия огромного числа выдающихся специалистов в данной области.
Ввиду этого можно считать, что NP-полные задачи являются труднорешаемыми со всех практических точек зрения,
хотя, повторяем, строгое доказательство этого составляет одну из центральных открытых проблем современной математики." (**)

рассуждения о списках публикаций, посвящённых (не)разрешимости проблемы P =? NP,
можно полистать в таких-то и таких-то трудах..

кроме P и NP умными дядями обнаружены и другие классы сложности:
P, NP, Co-NP, NP-C, Co-NP-C, NP-hard, UP, #P, #P-C, L, NL, NC, P-C, PSPACE, PSPACE-C..
остальные здесь https://en.wikipedia.org/wiki/List_of_complexity_classes
полный зоопарк классов здесь https://qwiki.caltech.edu/wiki/Complexity_Zoo

при обнаружении, что P = NP, все классы видимо сжимаются в один класс P,
а умные дяди при этом смеются..


вобщем, в этом семестре пришлось бродить где-то по краю математического языка..
где ввиду общепринятости посылок выводы ещё пока имеют смысл..
но уже попахивают абсурдом из-за искусственности последних и кривости первых